iT邦幫忙

2021 iThome 鐵人賽

DAY 13
0
自我挑戰組

每日攝取一點資料結構和演算法系列 第 13

Day13:[解題技巧]Two pointers -  雙指針

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20210913/20128604L9ZTWMidu4.jpg
雙指針算是一個解題蠻常用的小技巧,雙指針指的是用兩個指針對整個資料做遍歷,而雙指針又依照移動的方向性,分為對撞指針(反方向)和快慢指針(同方向)。

對撞指針

兩個指針為相反方向,通常一個在起點,一個在終點,慢慢向中間靠攏,在起始點的通常命名為left,在終點是right,那麼就用經典的two sum來示範雙指針吧!

注意:如果要用雙指針解這題 ,陣列必須要是有依序排列過的

two sum的題目為給定一個陣列arr和目標數target,arr[x] +arr[y] = target,請回傳arr[x], arr[y]

Example : 有一個排序過的陣列為[2, 3, 5, 9, 11],請問陣列中的哪兩個數字相加會等於目標數8呢?

實作步驟如下:
1.在起點設置左指針,在終點設置右指針
https://ithelp.ithome.com.tw/upload/images/20210913/20128604mngyCM5paX.png

2.此時因為2+11 = 13 大於我們的目標數8, 所以將右指針移動到9的位置
https://ithelp.ithome.com.tw/upload/images/20210913/201286044qxyiRjZ7N.png

3.結果2+9 = 11,還是大於8 ,所以又把右指針移到5的位置
https://ithelp.ithome.com.tw/upload/images/20210913/20128604ErO33w2gax.png

4.2+5 = 7 ,不幸的小於目標數8 ,所以把左指針移動到3,這時候就會發現3 、5這個組合不就是我們要找的嗎?所以成功找到兩個加起來總和為8的數字了!
https://ithelp.ithome.com.tw/upload/images/20210913/20128604mxHTTQ1dr7.png

用js實作雙指針

const twoSum = (arr, target) => {
    let left = 0;
    let right = arr.length - 1;
    while (left < right) {
        if (arr[left] + arr[right] === target) {
            return [arr[left], arr[right]];
        }
        if (arr[left] + arr[right] > target) {
            right--;
        } else {
            left++;
        }
    }
    return null;
};

twoSum([2, 3, 5, 9, 11], 8);

快慢指針

可以想像是程式界的龜兔賽跑,兩個指針的移動方向均為相同方向,但移動的速率為一快一慢。

題目範例:檢查str2是否為str1的subSequence,str1 = forever love,str2 = love

實作步驟如下:

1.紅色指針是快指針,黃色是慢指針,一開始兩種指針都會在起始點
https://ithelp.ithome.com.tw/upload/images/20210913/20128604nBpcr3dOEP.png

2.快指針每次都會移動一格,慢指針則是必須符合條件才會移動,移動條件:當快指針指向的字母與慢指針相同時
https://ithelp.ithome.com.tw/upload/images/20210913/20128604SgnEVLvO6r.png

3.不幸的因為一直不符合條件,所以只有快指針一路往後走
https://ithelp.ithome.com.tw/upload/images/20210913/20128604UhxzLygHgQ.png

4.好不容易,當快指針指到l,終於符合條件了!所以慢指針就可以前進一格
https://ithelp.ithome.com.tw/upload/images/20210913/20128604eDc7DdtlcQ.png

5.當慢指針指到最後一格的時候,就代表love的確是forever love的subSequence
https://ithelp.ithome.com.tw/upload/images/20210913/201286043Zik92ErMv.png

用js實作快慢指針

const isSubsequence = (str1, str2) => {
    if (str1.length === 0) return true;

    let slow = 0;
    let fast = 0;

    while (fast < str2.length) {
        if (str1[slow] === str2[fast]) {
            slow++;
        }
        if (slow >= str1.length) {
            return true;
        }
        fast++;
    }
    return false;
};

isSubsequence("love", "forever love");

快慢指針的解題方法蠻常被運用在Linked List的題型上面,像是反轉Linked List或是確認該Linked List是否有Cycle(如下圖)

https://ithelp.ithome.com.tw/upload/images/20210913/20128604BapkzQ6g9v.png
圖片來源:leetcode 141. Linked List Cycle

https://ithelp.ithome.com.tw/upload/images/20210913/20128604VqfNiK61Wy.png
檢查Linked List是否有Cycle可以這樣寫


上一篇
Day12:[資料結構]Binary Tree -  Traversal
下一篇
Day14:[解題技巧]Recursive - 遞迴
系列文
每日攝取一點資料結構和演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言